package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/24 17:11
 * @description <p>最多删除一个字符得到回文 </p>
 */

/**
 * 题目：给定一个字符串，请判断如果最多从字符串中删除一个字符能
 * 不能得到一个回文字符串。例如，如果输入字符串"abca"，由于删除字符'b'
 * 或'c'就能得到一个回文字符串，因此输出为 true。
 */
public class toOffer3_3_19 {
    public static void main(String[] args) {
        String s = "eeccccbebaeeabebccceea";
        System.out.println(validPalindrome(s));
    }

    /**
     * 双指针+贪心
     *
     * @param s
     * @return
     */
    public static boolean validPalindrome(String s) {
        int slow = 0;
        int fast = s.length() - 1;

        while (fast >= slow) {
            char start = s.charAt(slow);
            char end = s.charAt(fast);
            if (start == end) {
                fast--;
                slow++;
            } else {
                return validPalindrome(s, slow + 1, fast) || validPalindrome(s, slow, fast - 1);
            }
        }
        return true;
    }

    public static boolean validPalindrome(String s, Integer slow, Integer fast) {
        for (int i = slow , j = fast ; i < j ; ++i , --j) {
            char start = s.charAt(i);
            char end = s.charAt(j);
            if (start != end) {
                return false;
            }
        }
        return true;
    }

    /**
     * （该方法超时）
     * 思路：
     * 先判断s是不是回文，不是再继续
     * 不是的话就遍历s，从头开始删除一个数，然后构造新的字符串，再判断这个字符串是不是回文
     *
     * @param s
     * @return
     */
    public static boolean validPalindrome1(String s) {
        //判断s是不是回文
        if (judge(s)) {
            return true;
        } else {
            for (int i = 0; i < s.length() / 2; i++) {
                String newStr = s.substring(0, i) + s.substring(i + 1);
                if (judge(newStr)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断一个str是否对称
     *
     * @param str
     * @return
     */
    public static boolean judge(String str) {
        String newStr = new StringBuilder(str).reverse().toString();
        if (str.equals(newStr)) {
            return true;
        }
        return false;
    }
}
